package queue;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的层序遍历 -102
 *
 * @author yyz
 * @create 2023-12-31 16:35
 */
public class 二叉树的层序遍历 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(TreeNode left, int val, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 该方法实现了二叉树的层序遍历。
     * 使用队列来辅助遍历，首先将根节点加入队列，
     * 然后对队列进行循环直到队列为空，每次循环都处理当前层的节点，并将下一层的节点加入队列。
     * 最终返回一个列表，列表中的元素表示每一层的节点值。
     *
     * @param root 二叉树的根节点
     * @return 层序遍历结果
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>(); // 用于存储层序遍历结果的列表

        if (root == null) {
            return result; // 如果根节点为空，则返回空列表
        }

        Queue<TreeNode> treeNodes = new LinkedList<>(); // 用于存储待遍历节点的队列
        treeNodes.offer(root); // 将根节点加入队列
        int c1 = 1; // 当前层的节点数，初始为1，表示根节点

        while (!treeNodes.isEmpty()) { // 当队列不为空时，继续遍历
            int c2 = 0; // 下一层的节点数，初始为0

            List<Integer> level = new ArrayList<>(); // 存储当前层的节点值
            for (int i = 0; i < c1; i++) { // 遍历当前层的节点
                TreeNode poll = treeNodes.poll(); // 出队一个节点

                if (poll.left != null) { // 如果左子节点不为空
                    treeNodes.offer(poll.left); // 将左子节点加入队列
                    c2++; // 下一层节点数加1
                }
                if (poll.right != null) { // 如果右子节点不为空
                    treeNodes.offer(poll.right); // 将右子节点加入队列
                    c2++; // 下一层节点数加1
                }
                level.add(poll.val); // 将当前节点的值加入当前层的列表
            }

            c1 = c2; // 更新当前层节点数为下一层节点数
            result.add(level); // 将当前层的节点值列表加入最终结果列表
        }

        return result; // 返回层序遍历结果
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(
                        new TreeNode(4),
                        2,
                        new TreeNode(5)
                ),
                1,
                new TreeNode(
                        new TreeNode(6),
                        3,
                        new TreeNode(7)
                )
        );

        List<List<Integer>> lists = new 二叉树的层序遍历().levelOrder(root);
        System.out.println(lists);
    }
}
